package com.gwcloud.leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode078 
* @author      : ganwei 
* @date        : 2020年5月6日 
* @Description : leetcode 78 子集 回溯算法排列所有可能性 
*/
public class Leetcode0078 {
	
	List<List<Integer>> result = new ArrayList<>();
	int n,k;
	
    public void backtrack(int index, ArrayList<Integer> li, int[] nums) {
    	if(li.size() == k) {
    		result.add(new ArrayList<Integer>(li));
    		return;
    	}
    	for(int i = index; i < n; i++) {
    		li.add(nums[i]);
    		backtrack(i + 1, li, nums);
    		li.remove(li.size()-1);
    		
    	}
    }
	
    /**
	 * -解题思路，回溯算法
	 */
    public List<List<Integer>> subsets(int[] nums) {
    	n = nums.length;
        for(k = 0; k <= n; k++) {
        	backtrack(0,new ArrayList<Integer>(),nums);
        }
        
    	return result;
    }    
	/**
	 * -主函数
	 */
	public static void main(String[] args) {
		Leetcode0078 l078 = new Leetcode0078();
		int[] nums = {1,2,3};
		l078.subsets(nums);
		for(List<Integer> l : l078.result) {
			for(Integer n : l) {
				System.out.print(n+" ");
			}
			System.out.println();
		}
	}
}
